﻿public class Solution
{

    private IList<IList<string>> result = new List<IList<string>>();
    private IList<string> res = new List<string>();
    public IList<IList<string>> SolveNQueens(int n)
    {
        bool[] used = new bool[n];
        Trackbacking(n, 0, used);
        return result;
    }

    private void Trackbacking(int n, int cur, bool[] used)
    {
        // 找到一种方案
        if (cur == n)
        {
            result.Add(new List<string>(res));
            return;
        }
        
        // 横向搜索
        for (int i = 0; i < n; i++)
        {
            if (used[i]) continue;
            if (IsValid(n, cur, i))
            {
                char[] chars = new char[n];
                Array.Fill(chars, '.');
                chars[i] = 'Q';
                res.Add(new string(chars));
                used[i] = true;
                Trackbacking(n, cur + 1, used);
                used[i] = false;
                res.RemoveAt(res.Count - 1);
            }
        }
    }
    /// <summary>
    /// 判断该位置是否可以放置皇后
    /// </summary>
    /// <param name="n">n*n的棋盘格</param>
    /// <param name="cur">当前所在行，0开始</param>
    /// <param name="i">当前所在列，0开始</param>
    /// <returns></returns>
    /// <exception cref="NotImplementedException"></exception>
    private bool IsValid(int n, int row, int cul)
    {
        // 左上角没有皇后
        int i = row, j = cul;
        while (i > 0 && j > 0)
        {
            i--;
            j--;
            if (res[i][j] == 'Q') return false;
        }
        
        // 右上角
        i = row; j = cul;
        while (i > 0 && j < n-1)
        {
            i--;
            j++;
            if (res[i][j] == 'Q') return false;
        }

        return true;
    }

    public static void Main(string[] args)
    {
        int n = 4;

        Solution solution = new Solution();
        IList<IList<string>> result = solution.SolveNQueens(n);

        foreach (IList<string> res in result)
        {
            foreach (string r in res)
            {
                Console.Write($"{r} ");
            }
            Console.WriteLine();
        }
    }
}